package com.xiaoyu.dfs;

/**
 * @program: DS_and_A
 * @description:  岛屿的周长
 * 给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
 *
 * 网格中的格子 水平和垂直 方向相连（对角线方向不相连）。
 * 整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
 *
 * 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。
 * 格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
 *
 * 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
 * 输出：16
 * 解释：它的周长是上面图片中的 16 个黄色的边
 *
 * @author: YuWenYi
 * @create: 2021-06-04 10:37
 **/
public class IslandPerimeter_463 {
    //右,上,左,下
    public static final int[][] DIRECTIONS = {{0,1},{-1,0},{0,-1},{1,0}};
    public int[][] grid;   //使用全局变量,保证全局就只有一个grid
    public int perimeter = 0;  //周长

    public int islandPerimeter(int[][] grid) {
        int row = grid.length;;
        int col = grid[0].length;
        this.grid = grid;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1){
                    dfs(i,j);
                    break;  //因为题目说只有一个岛,所以找到了该岛的入口就行,dfs遍历完之后就没有岛了,直接break
                }
            }
        }
        return perimeter;
    }

    public void dfs(int row,int col){
        //如果不在格子里,或者在水里,周长就+1
        if (!inGrid(row,col) || grid[row][col] == 0){
            perimeter++;  //周长++;
            return;
        }
        if (grid[row][col] == 1){
            grid[row][col] = 2;
            for (int[] direction : DIRECTIONS) {
                int nRow = row + direction[0];
                int nCol = col + direction[1];
                dfs(nRow, nCol);
            }
        }
    }
    public boolean inGrid(int row,int col){
        return row>=0 && row < grid.length && col>=0 && col < grid[0].length;
    }

    public static void main(String[] args) {
        int[][] grid = {
                {0,1,0,0},
                {1,1,1,0},
                {0,1,0,0},
                {1,1,0,0}
        };
        IslandPerimeter_463 perimeter_463 = new IslandPerimeter_463();
        System.out.println(perimeter_463.islandPerimeter(grid));
    }
}
